//给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
//
// 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
//
//
//
// 示例 1：
//
//
//输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
//
//
// 示例 2：
//
//
//输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
//     注意，你可以重复使用字典中的单词。
//
//
// 示例 3：
//
//
//输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 300
// 1 <= wordDict.length <= 1000
// 1 <= wordDict[i].length <= 20
// s 和 wordDict[i] 仅有小写英文字母组成
// wordDict 中的所有字符串 互不相同
//
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 👍 1370 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.List;

@SuppressWarnings("all")
//Java：单词拆分
public class 单词拆分 {
    public static void main(String[] args) {
        Solution solution = new 单词拆分().new Solution();
        // TO TEST
        List<String> wordDict = Arrays.asList("car", "ca", "rs");
        solution.wordBreak("cars", wordDict);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean exsit;

        public boolean wordBreak(String s, List<String> wordDict) {
            return dp(s, wordDict);
        }

        public boolean dp(String s, List<String> wordDict) {

            boolean[] dp = new boolean[s.length() + 1];
            dp[0] = true;
            for (int i = 1; i < dp.length; i++) {
                for (String word : wordDict) {
                    if (i >= word.length()) {
                        dp[i] = dp[i - word.length()] && s.startsWith(word, i - word.length());
                    }
                    if (dp[i])
                        break;
                }
            }

            return dp[dp.length - 1];
        }

        public boolean dfs(String s, List<String> wordDict) {
            StringBuilder path = new StringBuilder();
            wordDict.sort((o1, o2) -> o2.length() - o1.length());
            dfs(s, wordDict, path);
            return exsit;
        }

        private void dfs(String s, List<String> wordDict, StringBuilder path) {

            if (path.length() == s.length()) {
                exsit = true;
                return;
            }

            for (String word : wordDict) {
                if (!s.startsWith(word, path.length()))
                    continue;
                path.append(word);
                dfs(s, wordDict, path);
                if (path.length() == s.length())
                    return;
                path.delete(path.length() - word.length(), path.length());
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}
